#ifndef _ARBRE
#define _ARBRE

#include "structure_index.hpp"

// Structure contenant c_i (chained_index) et nb_nodes
// Stockage des nbs de noeuds et des mots avec lignes
struct s_item
{
  chained_index c_i;
  int nb_nodes;
};

typedef s_item * list_item;

// Structure contenant item (list_item)
// Contient le mot et son nbr de noeud
// Liaison du sous arbre droit et gauche
struct node
{
  list_item item;
  node * left;
  node * right;
};

typedef node * tree;

// Initalisation de t a NULL
void create_tree(tree & t);

// Creer un noeud a partir de c_i (chained_index) et le rajoute a t (tree)
void create_node(tree & t,chained_index & c_i);

// Initialisation de t avec les mots de lindex
void initialise_tree(tree & t,chained_index & c_i);

// Affichage de larbre
void affiche_tree(const tree & t,int h=0);

// Suppression de larbre
void delete_all_tree(tree & t);

// Ajouter la ligne du mot si on la trouve dans la liste des mots du text
// stocker dans c_w
void add_ligne_tree(tree & t,chained_word & c_w);

// Fonction de partition_r du cours
// Elle permet partitionner un arbre en fonction du noeud
void partition_r(tree & t,int nb_noeud);

// Fonction de rotation dun noeud dun arbre a droite
// Mise a jour du nombre de noeud de larbre
void rotation_right(tree & t);

// Fonction de rotation dun noeud dun arbre a gauche
// Mise a jour du nombre de noeud de larbre
void rotation_left(tree & t);

// Equilibre un arbre
void equilibre_tree(tree & t);

#endif
